package com.le.medium.class5;

import org.junit.Test;

/**
 * 在迷迷糊糊的大草原上，小红捡到了n根木棍，第i根木棍的长度为i， 小红现在很开心。想选出其中的三根木棍组成美丽的三角形。
 * 但是小明想捉弄小红，想去掉一些木棍，使得小红任意选三根木棍 [都不能] 组成三角形。
 * 请问小明最少去掉多少根木棍呢？ 给定N，返回至少去掉多少根？
 * <p>
 * 思路：
 * 任意三根都组不成三角形 ==》 斐波那契数列任意三项都组不成三角形，且最小
 * 第三项等于前两项之和 最少
 * ==> 在1..n 范围内，有几个斐波那契数列， 去掉第一项
 */
public class Problem02_DeleteWood {

    // 1 2 3 4 5 6 7 8 ...
    public static int minDelete(int m) {
        // 1 2 3 比不能组成三角形
        if (m < 4) {
            return 0;
        }
        int count = 3;
        int k2 = 2;
        int k1 = 3;
        while (k1 + k2 <= m) {
            count++;
            k1 += k2;
            k2 = k1 - k2;
        }
        return m - count;
    }

    public static int minDelete1(int m) {
        if (m < 4) {
            return 0;
        }
        int pre = 1;
        int cur = 1;
        int temp = 0;
        int count = 0;
        while (cur <= m) {
            count++;
            temp = cur;
            cur += pre;
            pre = temp;
        }
        return m - count;
    }

    @Test
    public void test() {
        int test = 9;
        System.out.println(minDelete(test));
        System.out.println(minDelete1(test));
    }
}
